This invention relates to electronic transactions, and more specifically to secure function evaluation (SFE) techniques that provide privacy to the parties. This invention is especially, but not exclusively, suited to the SFE of functions implemented by circuits containing exclusive OR (XOR) gates. A Universal Circuit which contains many XOR gates can benefit from construction in accord with this invention. This invention is particularly, but not exclusively, suitable for evaluation of private functions.
SFE implementations have been disclosed, e.g. see “Fairplay—A Secure Two-party Computation System” by D. Malkhi, N. Nisan, B. Pinkas and Y. Sella, USENIX 2004. Two-party general secure function evaluation (SFE) allows two parties to evaluate any function on their respective inputs x and y, while maintaining privacy of both x and y. SFE algorithms enable a variety of electronic transactions, previously impossible due to mutual mistrust of participants. Examples include auctions, contract signing, distributed database mining, etc. As computation and communication resources have increased, SFE has become practical. Fairplay is an implementation of generic two-party SFE with malicious players. It demonstrates the feasibility of SFE for many useful functions, represented as circuits of up to about 106 gates. Another example of a SFE protocol implementation is “Y Lindell, B Pinkas, N. Smart, ‘Implementing Two-party Computation Efficiently with Security Against Malicious Adversaries’, SCN 2008”.
The SFE of private functions (PF-SFE) is an extension of SFE where the evaluated function is known only by one party and needs to be kept secret (i.e. everything besides the size, the number of inputs and the number of outputs is hidden from the other party). Examples of private functions include airport no-fly check function, credit evaluation function, background- and medical history checking function, etc. Full or even partial revelation of these functions opens vulnerabilities in the corresponding process, exploitable by dishonest participants (e.g. credit applicants), and is desired to be prevented.
The problem of PF-SFE can be reduced to the “regular” SFE by evaluating a Universal Circuit (UC) instead of a predetermined circuit defining the evaluated function. A UC can be thought of as a program execution circuit capable of simulating any circuit C of certain size, given the description of C as input. Therefore, disclosing the UC does not reveal anything about C, except its size. The player holding C simply treats the description of C as an additional (private) input to the SFE.
A PF-SFE can utilize computer simulated Y and X switching blocks as illustrated by FIGS. 1 and 2, respectively, interconnected to perform the required function logic for a programmable permutation network of a UC. The illustrated Y switching block of FIG. 1 illustrates a single output that has a value selected to be one of its two inputs. The Y switching block is controlled to determine which of the two inputs is selected as the output. The X switching block of FIG. 2 has two outputs and two inputs where one output receives one of the two inputs and the other output receives the other input. The X switching block is controlled to determine which of the first and second inputs appears on the respective first and second outputs.
A known SFE implementation of a Y block uses a computer simulation of a 3-input gate (the two inputs of the Y block, and an additional control input) with a stored “garbled” table of 23=8 encrypted table entries. A garbled table contains stored garbled values created using circuit input/output values that are transformed by mathematically applying secret values (garbled values) so that a person observing a garbled value cannot determine the corresponding circuit input/output values. Each garbled value may define a wire (input, output, control input) associated with a simulated circuit used to implement a universal circuit. Similarly, a known X block for use in an SFE implementation utilizes a computer simulation of two 3-input garbled gates (one for each of its two inputs) resulting in a garbled table of 2×23=16 table entries. Typical UCs will employ a substantial number of such gates resulting in a large number of corresponding table entries.